package two.chapter_1.c1_4;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import two.chapter_1.c1_1.Printer;

import java.util.Arrays;

public class Ex1_4_16 {


    public static void main(String[] args) {

        // int a[]={-10,-5,-2,0,2,4,9,20,50};

        double MAX = 1.0;
        int N = 10000;
        double a[] = new double[N];
        for (int i = 0; i < N; i++) {
            a[i] = StdRandom.uniform(0d, MAX);
        }
        //Arrays.sort(a);
        // Printer.printArray(a);
        Stopwatch stopwatch = new Stopwatch();
        nearest(a);//平方级别
        StdOut.println(stopwatch.elapseTime());

        Stopwatch stopwatch1 = new Stopwatch();
        nearestFast(a);//线性对数级别
        StdOut.println(stopwatch1.elapseTime());


        farthest(a);

        farthestFast(a);
    }

    /**
     * 平方级别
     *
     * @param a
     */
    private static void nearest(double a[]) {
        double min = Double.MAX_VALUE;
        int indexI = -1;
        int indexJ = -1;
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                double delta = Math.abs(a[i] - a[j]);
                if (delta <= min) {
                    min = delta;
                    indexI = i;
                    indexJ = j;
                }
            }
        }
        StdOut.println("min:" + min + "  indexI:" + indexI + "  indexJ:" + indexJ);
    }

    /**
     * 线性对数级别，NlogN   时间主要消耗在排序上
     * 差值最小：
     * 对于排序后的数组 只需比较左右两个数
     *
     * @param a
     */
    private static void nearestFast(double a[]) {
        Arrays.sort(a);
        double min = Double.MAX_VALUE;
        int indexI = -1;
        int indexJ = -1;
        for (int i = 0; i < a.length - 1; i++) {
            double delta = Math.abs(a[i] - a[i + 1]);
            if (delta <= min) {
                min = delta;
                indexI = i;
                indexJ = i + 1;
            }
        }
        StdOut.println("min:" + min + "  indexI:" + indexI + "  indexJ:" + indexJ);
    }

    /**
     * 线性对数级别
     * 对于有序的数组，两者之差最大值的绝对值 肯定是   第一个-最后一个
     *
     * @param a
     */
    private static void farthest(double a[]) {
        Arrays.sort(a);
        int indexI = 0;
        int indexJ = a.length-1;
        double max = Math.abs(a[0] - a[a.length - 1]);


        StdOut.println("max:" + max + "  indexI:" + indexI + "  indexJ:" + indexJ);
    }

    /**
     * 线性级别
     *
     * 只要在遍历过程中找到最大值和最小值即可
     * @param a
     */
    private static void farthestFast(double a[]) {

        int indexI = -1;
        int indexJ =-1;
        double max=Double.MIN_VALUE;
        double min=Double.MAX_VALUE;
        for (int i=0;i<a.length;i++){
            double val=a[i];
            if (val<min){
                min=val;
                indexI=i;
            }
            if (val>max){
                max=val;
                indexJ=i;
            }
        }

        double farthest=max-min;


        StdOut.println("max:" + farthest + "  indexI:" + indexI + "  indexJ:" + indexJ);
    }
}
